For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

2
votes
3answers
49 views

How many ways can we split a group of $n$ elements into groups of different sizes such that each group contains more than $1$element

let's assume $p[n]$ is the name of this partitioning method Let's see some examples: $n=3$: all possibilities are: $[(3,0),(2,1),(1,1,1)]$ all cases don't meet the condition $minSize > 1$ so ...
1
vote
2answers
29 views

Proof that all n-length subsets have been generated from a set.

I have a function in a computer program that generates integer subsets within an integer set. The function takes an set of sequential numbers and finds all the possible subsets of a given length. The ...
4
votes
2answers
65 views

Ways to form a committee - why is this approach incorrect?

I have the following question: If there are 7 women and 9 men, how many ways are there to select a committee of 5 members if at least 1 man and 1 woman must be on the committee? I have found the ...
-2
votes
2answers
94 views

Combinatorial homework problem.

This is for homework so I don't want any solutions. Just some guidance. Problem: Alice has $10$ balls (all different). First, she splits them into two piles; then she picks one of the piles with at ...
2
votes
2answers
44 views

20 types of candy available. How many ways can you put exactly 2 types of candy in a box with 10 spaces?

I think first you find the number of ways to choose your $2$ types via combination, and then putting them in the box is just with replacement, $n^k$. This will also count where all $10$ are the same ...
2
votes
3answers
33 views

Calculate number of (four-letter) strings that contain exactly two matching characters (s)

The following problem refers to strings in A, B, ..., Z. Question: How many four-letter strings are there that contain exactly two S's? I used the formula in this answer to come up with the ...
0
votes
0answers
17 views

combinatorial proof of Vandermonde's Identity [duplicate]

So I can not figure out the combinatorial proof for Vandermonde's Identity for the example $\sum_{i=0}^k \binom {k} {i}^2 = \binom {2k} {k}$ Any help would be appreciated. Figured it out, thanks :)
3
votes
0answers
33 views

Forming the graph $G$ from elements of the cut and cycle space, using a weird hint

I'm working through a set of lecture notes on my own, and since there is no class, there are no immediate faculty members available to ask questions to. I've managed to finish most exercises quite ...
2
votes
1answer
77 views

Lengths of the shortest “simple” equation, that use only the number '1', equal to a given natural numbers.

Is there a formula, for determining the length of the shortest formula, that uses only the number '1', parenthesis, and the hyperoperations $\{\{+, - \}, \{\times, / \}, \{\text{^}, \log_N\}, \{↑,?\}, ...
2
votes
3answers
64 views

Simplifying $\sum\limits_{k=0} {n \brack 2k}$ [closed]

Simplify $\sum\limits_{k=0} {n \brack 2k}$ where ${n \brack 2k}$ is Stirling's number of the first kind and $n \geq 0$
2
votes
1answer
58 views

Does anybody spot anything familiar in this integer sequence?

$0,3,9,21,40,67,106,154,220,298,395,510,644,\dots$ These are the maxima of the distances between permutations of length $n$ up to $n=13$ according to a modified version of Spearman's footrule number ...
1
vote
1answer
34 views

In how many ways can 3 monitors be oriented and placed on a desk?

There are $3$ distinguishable monitors and each monitor can be oriented in $4$ unique ways. In how many ways can you arrange them on a desk? ($3$ positions in total) My attempt: There are $3!$ ways ...
0
votes
1answer
23 views

Is there a definitive formula for this combination?

To help Lavanya learn all about binary numbers and binary sequences, her father has bought her a collection of square tiles, each of which has either a 0 or a 1 written on it. Her brother Nikhil has ...
0
votes
1answer
45 views

Placing identical balls into identical boxes

If $12$ identical balls are to be placed in $3$ identical boxes, then the probability that one of the boxes contains exactly $3$ balls is? This question has already been posed on this site, but in ...
0
votes
1answer
51 views

Calculate number of students who failed. [closed]

60 students appeared in a test consisting of three Papers I,II and III. Of these students, 25 passed in Paper I, 20 in Paper II and 8 in Paper III. Further, 42 students passed in at least one of ...
-1
votes
0answers
53 views

Is there a formula for $\sum_{r=1}^x({n+r-1})Cr$? [duplicate]

I have an algorithm who is something like this : MOD = 1000003 ans = 0 while (r) : ans = (ans + nCrMod(n + r - 1, r, MOD))%MOD r-- print ans ...
0
votes
0answers
40 views

Counting all permutations(repeating) with no adjacent elements equal and m majority elements.

Counting all permutations(repeating) of 1 to n which have size n. 1. with no adjacent elements equal, and 2. m majority elements(A element is majority element when it appears max number of times in ...
2
votes
1answer
27 views

Number of permutations with subset distance constraint

The problem is to calculate the number of all unique permutations of a string with repetitions. There is also a constraint for one subset elements to be spaced from each other. Typical input data is ...
2
votes
1answer
27 views

There are n balls and m colors, calculate the ways that color 1 appear most

Also, color 1 can be as many as others. for example: there 2 balls and 3 colors, we can color like that: 1 1, 1 2, 1 3, 2 1, 2 2, 2 3, 3 1, 3 2, 3 3 and 1 1, 1 2, 1 3, 2 1, 3 1 are the valid ...
0
votes
2answers
37 views

Permuation And Combination Based Problem - Arrangements Of People In A Row Of Cinema Hall In A Particular Manner

There are fifteen seats in the first row of a cinema hall.The torch man has the instruction that seat number 6 must be occupied.The number of ways in which 4 seats of the first row can be alloted so ...
0
votes
2answers
32 views

Finding the minimum wins in a round-robin tournament.

There are 16 teams in total. They are divided into two groups of 8 each. In a group, each team plays a single match against every other team. At the end of the round, top 4 teams go through to the ...
0
votes
0answers
24 views

A vector $\{0,1\}$ combinatorial question

How many different ways are there to choose $n$ distinct vectors in $\{0,1\}^{n}$ each of Hamming weight $w$ such that there is $k$ of them that will agree at exactly $s$ positions? Is there a nice ...
1
vote
2answers
39 views

In how many ways can you select one of the two but not both?

For this question: A committee of three boys and three girls is to be selected from a class of 14 boys and 17 girls. In how many ways can the committe be selected if: a.) Ana has to be on the ...
1
vote
1answer
87 views

How to compute the Mobius function

I have no clue how to begin this problem. It involves computing the Mobius inversion function $\mu$. This problem comes from Stanley's $\textit{Enumerative Combinatorics}$, vol 1, problem 70, Chapter ...
0
votes
1answer
35 views

How many strictly increasing functions can be formed?

Let $A=\{x \in\mathbb{N}~|~x\leq10\}$, $B=\{x \in\mathbb{N}~|~x\leq100\}$ $f: A \longrightarrow B$ How many strictly increasing functions can be made? I thought: I have $91$ options for $f(1)$ ...
1
vote
0answers
20 views

How many ways can you pick from a list when for each pick you can either pick 1 or 2 items from the list? [duplicate]

Suppose you have x amount of bagels, each day you must eat 1 bagel minimum or 2 bagels maximum..how many different ways can you eat all the bagels?
7
votes
0answers
69 views

Showing that poset of set of supports of a vector space is semimodular

Let $W$ be a subspace of the vector space $\mathbb{K}^n$, where $\mathbb{K}$ is a field of characteristic $0$. The support of a vector $v = (v_1,\ldots, v_n) \in \mathbb{K}^n$ is given by ...
0
votes
0answers
5 views

Hereditary Discrepancy Estimation

It is known that it is NP-hard to distinguish whether a set system has discrepancy $0$ or $O(\sqrt{n})$, given that the set system has $n$ elements and $m = O(n)$ sets. However, does the same hold ...
0
votes
1answer
15 views

Probability of an elevator rising to a certain floor at most and exactly

In a $10$ story building, $5$ people enter an elevator on ground level and press the floor buttons $(1-10)$ in random and independently. What is the probability that the elevator will rise ...
1
vote
2answers
17 views

On estimating a prime related Diophantine equation related to a partition .

A friend gave me the following algebraic combinatorics question which I couldn't solve Let $p$ be a prime number and $f(p)$ the smallest integer for which there exists a partition of the set $\{2,3, ...
0
votes
2answers
24 views

Discrete Math Combinatorics, permutation, one-to-one proof

I am having trouble getting started with the following proof: (This is homework, so I'd appreciate a nudge in the right direction.) Let m, r $\in$ N with 0 $\leq$ r $\leq$ m. Prove that the number of ...
1
vote
0answers
27 views

Counting Reals with the Lambda Calculus

I have come up with an explanation for the countability of the reals and I am wondering where I went wrong. In the lambda calculus, all integers can be represented by functions fairly simply. ...
3
votes
1answer
38 views

Finding the probability that in ten dice throws the digit six will appear at least five times

Find the probability that in ten dice throws the digit six will appear at least five times. My attempt: Using complement, six will appear at most 4 times. I'm pretty sure that $1-(\frac 5 6)^4$ ...
0
votes
0answers
57 views

Strange Candy Distribution, No two adjacent students get same number of candies.

There are N students and professor has N2 candies. Students get at least 1 and at most N candies and no two adjacent students should get same number of candies. Professor makes the frequency chart for ...
0
votes
1answer
184 views

Find the Number of non decreasing Sequence

We know the No. of Non decreasing Sequence of length N is (9+N)CN How can we find the number of decreasing Sequence in a ...
0
votes
2answers
65 views

Summation of Binomial Coffecient [duplicate]

What will be the summation of this Series $$\binom{10}{1} + \binom{11}{2} + \binom{12}{3} +\cdots+\binom{10+n}{n+1}$$
0
votes
1answer
20 views

Method for finding permutation of n elements if you have all permutations of (n-1) elements

In the "The Art of Computer Programming Volume 1 third edition " chapter 1.2.5. Permutations and factorials professor Knuth introduces method for constructing all permutation of $n$ objects from ...
-1
votes
0answers
23 views

Arrange white and colored balls in cells

How many ways there are to arrange $2n$ white balls and $n$ colored balls (int $n$ colors) in $3n$ cells, such that exist a cell from the first 5 cells in which there are less than 3 balls? I know ...
0
votes
2answers
30 views

What is the probability that the digit $0$ will appear at least once and the digit $2$ will appear at least once?

Choosing a 6 digit random number, what is the probability that the digit $0$ will appear at least once and the digit $2$ will appear at least once? Using complement, we have the digits two or ...
0
votes
1answer
19 views

Unranking pseudo-random values to produce uniform distribution over all permutations

Following this question (and answers) on SO. The problem is to find a method to produce an unranking of combinatorial objects in random order, but in such a way that all possible orderings are ...
1
vote
0answers
30 views

Permutations of k types for a number smaller then total of k's (without replacement)

How can you find the number of permutations of a set of items grouped in different categories when you must choose less than the total of the set. For example, I have a set of $12$ songs that are in ...
0
votes
0answers
35 views

Combinatorics Summation Formula [duplicate]

Can anybody please tell me the summation formula for: $$\sum_{i=1}^NC(k+i-1, i) = ?$$ Where ' k ' is some constant. Here C(x, y) stands for Combinatorics formula e.g. C(12, 6) = 924.
0
votes
1answer
13 views

bounds on binomial coefficients

Do the standard upper bounds on the binomial coefficient $\binom{n}{k}$ still work well if $k=f(n)$ (by standard i mean for example $(\frac{en}{k})^{k}$ and $\frac{n^{k}}{k!}$)? In particular if ...
0
votes
0answers
18 views

What is the probability that a cluster of particles will contain some fraction of labeled particles, given total fraction of labeled particles?

Say you have a very large (but known) number of particles ($C$) and some known fraction of these particles are "labeled" ($F_L$). The particles spontaneously group into clusters of $n_c$ particles. ...
3
votes
1answer
62 views

Total number of unordered pairs of disjoint subsets of S

Let $S = \{1, 2, 3, 4\}$. Find the total number of unordered pairs of disjoint subsets of $S$. I know the answer is $41$ since it's solved in the book as the expression $$\frac{3^4 -1}{2!} +1 ...
2
votes
0answers
38 views

Representation of positive integers in pascal's triangle [closed]

Prove that every positive integer k, any positive integer n can be written as n = $x_1\choose1$ + $x_2\choose2$ + $x_3\choose3$ ...$x_k\choose k$ eg k=2 n= 5 = $2\choose1$ +$3\choose2$ Is this a ...
0
votes
2answers
21 views

Summation with Multiple Indices

How would the following summation work? $\sum_{r,s,t \ge 0_{r+s+t=n}} \binom{m_1}{r} \binom{m_2}{s} \binom{m_3}{t}$ How would you choose the value for the next integer in the series? For example, ...
2
votes
4answers
85 views

Find ways to pick 3 numbers such that their product is a multiple of 8

$Let$ $A=\{1,2,3,4,5,6,7,8,9\}$ How many ways are there to pick 3 non-repeated numbers from the set $A$ such that their product is a multiple of 8? My attempt: I need to fit three $2$s in the ...
0
votes
0answers
39 views

What would be the join and meet of this lattice?

I'm working on the following problem: Let $W$ be a subspace of the vector space $\mathbb{K}^n$, where $\mathbb{K}$ is a field of characteristic $0$. Let $L$ denote the set of supports of all vectors ...
2
votes
1answer
19 views

Set of pairwise sum is the same

Let $X=\{x_1,\ldots,x_n\},Y=\{y_1,\ldots,y_n\}$ be sets of pairwise distinct integers with $X\neq Y$. For which $n$ is it possible that $\{x_i+x_j\mid i<j\}=\{y_i+y_j\mid i<j\}$? For example, ...