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)

1
vote
0answers
131 views

Calculating the probability of letter assignment

We have 10 letters written to 10 different friends and the 10 addressed envelops. The letters are put into the envelops at random, that is, all 10! assignment are equally likely. (a) What is the ...
2
votes
1answer
188 views

How many ways to place n distingusishable balls into m distinguishable bins of size s?

Let there be $n$ distinguishable balls and $m$ distinguishable bins, each bin of size $s$, that is, we cannot place more than $s$ balls into it. How many possibilites are there to place the balls into ...
0
votes
1answer
25 views

Finding a seating arrangement of $4$ different people in $n$ rounds

I have a practical problem. I want to arrange a speeddate event with $24$ or $32$ people in $7$ rounds. I have a room with sufficiently many tables and I want $4$ people per table and each round must ...
1
vote
0answers
173 views

Counting the number of partitions having blocks of cardinality 2 and non-distinct elements

Say I have a set of integers $\{1,2,\cdots,n\}$, then there exists $B_n$ partitions of this set where $B_n$ is a Bell number. For instance, there are $B_3$=5 partitions of the set $\{1,2,3\}$: $$ ...
1
vote
0answers
44 views

Upper bound on number of ways to place $n$ indistinguishable objects into $k$ distinguishable intervals of size $s$

I need a simple, but tight upper bound on the number of ways to distribute some $n$ indistinguishable objects among $k$ distinguishable boxes of size $s$. The formula for this quantity is absolutely ...
1
vote
1answer
55 views

Count and description of vertices of certain faces - called CNTBFs - of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$

For $k \ge 1$, $d \ge 2$ and $k \le d - 1$, let ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ be the intersection of $k - 1$ facets of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$ with equations: ...
1
vote
1answer
376 views

How many 6 digit numbers with 2 or 3 repetitions allowed

Solution is pretty well known for the question: how many $6$ digit numbers can be written by using digits $0,..,9$, where, every digit can be used only once. However, while I was thinking today, I ...
3
votes
1answer
66 views

Combinatorics in chess

Let $ ABCD \ $ be an finite chessboard ($n*n$ tiles) where $A$ is the left lower corner and $C$ its opposite. Each tile is denoted by a square with length $L=1$. Our purpose is to determine the ...
0
votes
1answer
95 views

Problem finding $10$-combinations of multisets

Today I had my exam of discrete maths and was asked to find the: no. of $10$-combinations of multiset $\{\infty a,3b,6c\}$. What I did was that: consider set $A_1=$ no. of ways such that no ...
3
votes
2answers
38 views

Partitions without 2

How do I find the generating function for partitions of $n$ that have no part with size $2$? In general, how would I find this for partitions that have no part of size $k$?
1
vote
0answers
64 views

Filling a square table with numbers

Suppose we have integers from $1$ to $q$ and a square table of $p$ rows. Let $q \leq p^2$. Denote $C_i$ to be $i$-th column of the table. The table is filled with numbers from $1$ to $q$ in such way ...
2
votes
2answers
59 views

The smallest $n$ for which the sum of binomial coefficients exceeds $31$

I have a problem with the binomial theorem. What is the result of solving this inequality: $$ \binom{n}{1} + \binom{n}{2} + \binom{n}{3} + \cdots +\binom{n}{n} > 31 $$
2
votes
1answer
66 views

Number of unlabeled simple graphs with $n$ nodes even for all $ n\ge 5$?

The extended version of OEIS for the number of unlabeled simple graphs with $n$ nodes shows that the only odd number (besides the trivial cases $n = 0 $ and $n = 1$) is for $n=4$ ($11$ graphs). The ...
1
vote
0answers
134 views

n bins, m balls and m>n: Probability of at least r bin containing exactly k balls.When bins are numeret from 1…n and ball is equale.

I want to calculate this probability .In this question $N$ bins, $m$ balls: Probability of any bin containing *exactly* $k$ balls. calculate this but I can not understand this calculation.To be more ...
0
votes
2answers
43 views

I am kind of confused on how to solve this question. Can anyone help please

If we let $S$ be the set that is defined by the following two rules: 1 is an element of the set $s$ If $s$ is an element of the set $s$, then x+$2 \sqrt{x}+1$ is also an element of the set $s$ how ...
-1
votes
1answer
41 views

Prove that exists such sequence…

Given is a set of number: $$ {a_1, ... , a_{11} } $$ Prove that there exists a sequence of non-zero, that $$ x_1, ..., x_ {11} $$ of words from the set {1,0,1} that the number of: $$ x_1a_1 + ... + ...
0
votes
1answer
144 views

COmbinatoric : Guess who is the winner candidate?

National Radio Broadcast will put a contest to guess five winners out of twelve local boxers who will compete to win the best 5 boxers. All twelve boxers are equally good so the chance of winning is ...
0
votes
2answers
114 views

Ball Occupancy Problem

Suppose we put r balls at random in n boxes, i.e., all n r assignments of balls to boxes have equal probability. Let Ai be the event that the ith box is empty and Nn = the number of empty boxes. It is ...
1
vote
1answer
83 views

How many 4-digit integers greater than zero have 3 or 6 as their third digit and 3 as their first digit?

Questions like these are very common on PSAT and SAT tests, and I can never figure it out within a suitable amount of time. Is there an easier way to work through these kinds of problems without ...
2
votes
3answers
871 views

Permutations and Combinations? 3 digit number…

1) Make a 3 digit even number without repeated digits, using 0, 4, 5 , 6, 7. Also the first digit cannot be 0. 2)Arrange 12 books in a line, 4 of which are english, 3 of which are science, and 5 ...
0
votes
1answer
268 views

Permutations and Combinations. Arranging things to be adjacent etc…

How many ways to do the following tasks 1)Arrange 12 blocks in a line, 4 of which are green, 3 of which are blue, and 5 red, so that all blocks are adjacent. 2)Form an 8 digit number using each ...
2
votes
0answers
65 views

s4≀s2 visually?

What does the polytope whose symmetry is (exactly, not larger isomorphisms) s4≀s2 look like? Does anyone know of a full decomposition of its construction, i.e. lattices, hasse diagrams, cayley graphs, ...
0
votes
1answer
262 views

Combinations Problem - Arranging People in Rooms

A hostel has four vacant rooms. Each room can accommodate a maximum of four people. In how many different ways can six people be accommodated in four rooms. The answer is 4020. My case by case ...
0
votes
2answers
60 views

sum of the numbers of both subsets are equal.

Given a set of 10 numbers chosen from {10,11,...,99}. Prove that in this set there are two non-empty and different subsets such that the sum of the numbers of both subsets are equal. Please for ...
3
votes
3answers
97 views

Prove $\sum_{k=0}^{n}\frac{\binom{n}{k}(-1)^k}{k+1}$ = $\frac{1}{n+1}$

Any tips on where to start? I tried induction, using the inductive property of Binomial coefficients and the Mean Value Theorem for divided differences however I haven't made any progress.
2
votes
2answers
52 views

Prove that, given any positive integer n, some multiple of it must be of the form 99…900…0

Prove that, given any positive integer n, some multiple of it must be of the form 99...900...0 Give me a hand, please.
1
vote
1answer
81 views

octagonal number theorem $q$-Pochhammer symbol expression

Setting the exponents of this analogue of the series in Euler's Pentagonal Number theorem to be the octagonal numbers: $$U(q)= \sum_{n\in\mathbb{Z}} (-1)^{n}q^{n(6n-4)/2}$$ in mpmath: ...
1
vote
3answers
72 views

$2^n$ binomial theorem

How can I prove that $$2^n=2\left({n \choose 0}+{n \choose 2}+{n \choose 4}+\dots\right)$$ using the binomial theorem. I've tried expanding $(x-y)^n$ with multiple different values of $x$ and $y$ but ...
3
votes
1answer
51 views

solving a combinatorial problem

Alex has $N$ dice; each of them has $K$ faces numbered from $1$ to $K$. Now he has arranged the $N$ dice in a line. He can rotate/flip any die if he wants. How many ways he can set the top faces such ...
3
votes
1answer
156 views

A Law of Large Numbers Without Replacement

Let $(n_1,...,n_r)$ be $r$ positive integers, and let $n=n_1+...+n_r$. Fo each positive integer $m$ consider an urn containing $mn$ balls, of which $mn_1$ are of type 1,..., $mn_r$ of type r. For each ...
0
votes
1answer
40 views

Proving a combination problem?

Given n and r are positive integers, how should I go about proving this statement? I tried using the combination forumula but I didnt really came close of solving it. Any help is appreciated. ...
1
vote
2answers
71 views

$O(1)$ algorithm for coin change w/out nickels

For the coin changing problem in the case without nickels (only quarters, dimes, and pennies available), assuming you use quarters until $x < 50$ since it's better to use quarters for $x \geq 50$; ...
4
votes
2answers
1k views

Expected number of cycles in permutation

Consider a random permutation of $1,2,\ldots,n$. What is the expected number of cycles in it? I thought about using linearity of expectation, but here it's not clear how we can break down the main ...
4
votes
1answer
89 views

Properties of the 'forgotten' symmetric polynomials

In I.G. Mcdonald "Symmetric Functions and Hall Polynomials" pg.22, the forgotten symmetric functions $f$ are introduced very briefly as the result of applying an involution $\omega$ to the monomial ...
1
vote
1answer
29 views

Question regarding an algebraic manipulation in GFology

How does the author arrive at the last equality in the first line, i.e.$$\text{why is } [x^k]\frac{1}{1-y(1+x)} = \frac{1}{1-y}[x^k]\frac{1}{1-\left(\frac{y}{1-y}\right)x} \text{?}$$
1
vote
1answer
133 views

combination/induction question, number of ways you can divide n people into groups of 1 or 2

this is homework!! Let $n \geq 1$ be an integer and consider $n$ people $P_1,P_2,\ldots,P_n$. Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group ...
0
votes
3answers
93 views

Ways of spending money combinatorial problem

Suppose person X has $12$ dollars.In each of the first 5 days he buys one of the following items. 1.Item A for $1 2.Item B for $2 3.Item C for $3. In how many ways can he spend the money ...
0
votes
1answer
77 views

Combinatorial proof of an identity of Striling number of first kind

I can prove this identity using induction but i was looking for a combinatorial proof for this identity regarding stirling numbers of first kind. How should i proceed? Where, Thanks in advance.
5
votes
0answers
100 views

Number of restricted ways to two-color a necklace [duplicate]

There are $n$ beads placed on a circle, $n\ge 3$. They are numbered in random order as viewed clockwise. Beads for which the number of the previous bead is less than the number of a next bead are ...
5
votes
1answer
128 views

No. of integral solutions of $x_1+x_2+x_3+x_4=20.$

I've to solve a no. of questions of this type but don't get how to do it: Determine the no. of integral solutions of $x_1+x_2+x_3+x_4=20.$ given the constraint that $$1\leq x_1\leq ...
1
vote
2answers
55 views

Number of ways to group digits in {1,2,3,4,5,6,7,8,9} into numbers, while maintaining order

I have a set of integers from 1 to 9, call it A: $$A=[1,2,3,4,5,6,7,8,9]$$ How could I find the total number of possible combination of numbers within that set, while maintaining order? For example, ...
2
votes
2answers
487 views

How many 7-digit telephone numbers have an odd number of even numbers?

((7 choose 1)*5^7) + (7 choose 3)*5^7) + (7 choose 3)*5^7) + (7 choose 1)*5^7) This is how I attempted to solve the problem, but I'm not sure if its correct.
7
votes
1answer
104 views

Sets of size at least $k$ with intersection of size at most $1$ cool problem.

At the OMM School every student goes to at least $k$ classes and two classes have at most $1$ student in common. Prove there is a set of $k$ classes where all of those classes have the same amount of ...
3
votes
2answers
77 views

$P(AB=BA)$ , $A,B\in M_{3x3}(\mathbb Z/p\mathbb Z)$

Let $A,B\in M_{3x3}(\mathbb Z/p\mathbb Z)$ ($p$ a prime number). Find the probability $P$ that $AB=BA$ that is $P(AB=BA)$ $$A=\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} ...
0
votes
3answers
55 views

Number of ways to park $10$ cars

Given $10$ cars (5 Fords, 3 Dodges, and 2 Hondas), how many ways can the cars be parked if there are (a) $10$ spots available? (b) $15$ spots available? My solution: (a) ${10 \choose 5} + {5 \choose ...
1
vote
2answers
25 views

Sum of Cells in Corner and in Center of Magic Square

For the magic square of order 4, the sum of 4 cells in each corner and sum of 4 cells in the center is the same which is equal to 34. But I don't have idea how to prove it. Any hint?
2
votes
1answer
41 views

On the number of cycles and independent edges in $K_{8}$

I am trying to find the number of cycles and $K_{2}$'s in $K_{8}$. That is, partition $8$ into all the ways such that the lowest part can be a $2$, so we have $8 = 8$, $6+2$, $5+3$, $2+3+3$, $4+4$, ...
1
vote
2answers
221 views

How many Binary numbers?

How many binary numbers of length $n$ can be generated where $n > 7$ and the number either start with $000$ or end with $111$? My questions is, can I choose an $n$ randomly? For example, let's say ...
0
votes
1answer
63 views

Combo: Unambiguous expression - String

I am stuck on finding an unambiguous express so that it can produce all the strings in the given set, for the set of binary strings where for each block of zero's which are of length minimum 3 must be ...
6
votes
0answers
108 views

Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted $$b(1;n,k)=b(n,k)$$ These ...